Two-dimensional curves are the predominant data type in graphical information systems (GIS). Examples include roads, shorelines, and administrative boundaries. Typically these curves are stored as polylines. A polyline is a sequence of point coordinates that are connected by straight line segments. Storing GIS data as polylines is advantageous for various data manipulation and visualization techniques, such as zooming a map on a GPS device, but is inefficient in memory utilization.
It is not unusual for the points in a polyline to oversample the curve, meaning that the polyline uses more points than necessary to represent the curve. Oversampling is inefficient in terms of both memory usage and time required for processing and displaying the polyline. In addition, sampled data points typically include random error or noise, which can dominate the data values in the low-order bits.
Various conventional approaches describe methods for representing polyline data more efficiently. For example, methods described in U.S. Pat. No. 6,812,925 and U.S. Pat. No. 7,859,536 represent polylines with other simpler polylines. The method described in U.S. publication 2011/0087715 simplifies the polyline by representing a subset of points using a circular arc. However, those methods still can be suboptimal.